package com.example.sort28.heap;

/**
 * @description 堆排序
 * @auther lijiewei
 * @date 2021/11/22 16:39
 */
public class HeapSort {

    /**
     * 排序
     * @param arr 数组
     * @return
     * @author lijiewei
     * @date   2021/11/22 16:55
     */
    public static void sort(int[] arr) {
        if (arr.length <= 1) {
            return;
        }

        //1.建堆
        buildheap(arr);

        //2.排序
        int k = arr.length - 1;
        while(k > 0) {
            //将堆顶元素（最大）与最后一个元素交换位置
            swap(arr, 0, k);
            //将剩下元素重新堆化，堆顶元素变成最大元素
            heapify(arr, --k, 0);
        }
    }

    /**
     * 建堆
     * @param arr 数组
     * @return
     * @author lijiewei
     * @date   2021/11/22 17:23
     */
    private static void buildheap(int[] arr) {
        //(arr.length - 1)/2 为最后一个叶子节点的父节点
        //最后一个非叶子节点，依次堆化直到根节点
        for (int i = (arr.length - 1) /2; i>=0; i--) {
            heapify(arr, arr.length-1, i);
        }
    }

    /**
     * 堆化
     * @param arr 数组
     * @param n 最后堆元素的下标
     * @param i 要比较的元素下标
     * @return
     * @author lijiewei
     * @date   2021/11/22 17:25
     */
    private static void heapify(int[] arr, int n, int i) {
        while(true) {
            //最大值位置
            int maxPos = i;
            //与左子节点(i*2+1)比较，获取最大值位置
            if (i*2+1 <= n && arr[i] < arr[i*2+1]) {
                maxPos = i*2+1;
            }
            //最大值与右子节点（i*2+2）比较，获取最大值位置
            if (i*2+2 <= n && arr[maxPos] < arr[i*2+2]) {
                maxPos = i*2+2;
            }
            //最大值是当前位置结束循环
            if (maxPos == i) {
                break;
            }
            //与子节点交换位置
            swap(arr, i, maxPos);
            //以交换后的子节点位置继续往下对比
            i = maxPos;
        }
    }

    /**
     * 交换数组中两个数
     * @param arr 数组
     * @param i 交换的第一个元素
     * @param j 交换的第二个元素
     * @return
     * @author lijiewei
     * @date   2021/11/22 17:48
     */
    private static void swap(int[] arr, int i, int j) {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }
}
